|
This page last changed on Jan 27, 2008 by carlos.gonzalez.
Un Analizador Sintáctico Ascendente (Bottom-Up Parser) intenta encontrar una derivación derecha de la frase buscando lados derechos de producciones y reemplazándolos en cada paso por el no-terminal en el lado derecho correspondiente, hasta lograr una sustitución que produzca solo el símbolo inicial S.
El análisis ascendente consiste en partir desde una cadena buscando desde los elementos terminales (hojas) las producciones que generan esa cadena, intentando encontrar la raíz del árbol de derivación (axioma).
Ejemplo
Dada la gramática sobre el alfabeto que incluye paréntesis y la letra "a":
- S → ( L )
- L → L A
- L → A
- A → S
- A → a
Un analizador sintáctico ascendente llevaría a cabo los siguientes pasos para encontrar una derviación de la frase ((a)(a)a):
| ⋅((a)(a)a) |
shift |
| (⋅(a)(a)a) |
shift |
| ((⋅a)(a)a) |
shift |
| ((a⋅)(a)a) |
reduce 5 |
| ((A⋅)(a)a) |
reduce 3 |
| ((L⋅)(a)a) |
shift |
| ((L)⋅(a)a) |
reduce 1 |
| (S⋅(a)a) |
reduce 4 |
| (A⋅(a)a) |
reduce 3 |
| (L⋅(a)a) |
shift |
| (L(⋅a)a) |
shift |
| (L(a⋅)a) |
reduce 5 |
| (L(A⋅)a) |
reduce 3 |
| (L(L⋅)a) |
shift |
| (L(L)⋅a) |
reduce 1 |
| (L S⋅a) |
reduce 4 |
| (L A⋅a) |
reduce 2 |
| (L⋅a) |
shift |
| (La⋅) |
reduce 5 |
| (LA⋅) |
reduce 2 |
| (L⋅) |
shift |
| (L)⋅ |
reduce 1 |
| S⋅ |
end |
|
